const arr = [5, 4, 3, 2, 1];
/**
 * 外循环控制比较的轮数
 * 内循环控制每轮比较的次数
*/
function bubble(arr) {
    // 轮数(需要arr.length - 1轮)
    // 这里数组中一共有5个数，只需要把数组中最大的4个数依次放到数组末尾即可。
    for (let i = 0; i < arr.length - 1; i++) {
        // 每轮比较的次数
        // 减去1的原因：每一轮都不需要和自己比
        // 减去i的原因：比如说第二轮的话，i等于1，因为在第一轮的时候已经把数组中最大的元素放到了数组末尾，因此不需要再跟最后一个元素比较，因此需要减去i。以此类推，第三轮和第四轮也是同理。
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // let temp = arr[j];
                // arr[j] = arr[j+1];
                // arr[j+1] = temp;
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
    return arr;
}
console.log(bubble(arr)); // [1, 2, 3, 4, 5]

const arr = [12, 6, 23, 4, 36, 18];

function insert(arr) {
    const res = []; // 结果数组
    res.push(arr[0]); // 默认将第一项先放到结果数组中
    // 从第二项开始依次插入
    for (let i = 1; i < arr.length; i++) {
        // currentEle是当前要插入的元素
        const currentEle = arr[i];
        // 从后往前比
        for (let j = res.length - 1; j >= 0; j--) {
            if (currentEle > res[j]) {
                // 如果currentEle比res[j]大，则将currentEle插入到res[j]的前面
                // 所以这里splice方法的第一个参数是j+1，而不是j
                res.splice(j + 1, 0, currentEle);
                break;
            }
            // 上面的if语句会一直从后向前比较，直到和res中的第一项比较完
            if (j === 0) {
                // 走到这里说明，currentEle比res中的第一项还要小，直接插入到数组最前面即可
                res.unshift(currentEle);
            }
        }
    }
    return res;
}
console.log(insert(arr));

const arr = [12, 6, 23, 4, 36, 18];

function quick(arr) {
    // 第四步：结束递归(当arr中小于等于一项，则不用继续递归处理)
    if (arr.length <= 1) {
        return arr;
    }
    // 第一步：找到数组的中间项，并在原数组中将其移除
    const middleIndex = Math.floor(arr.length / 2); // 向下取整
    const [middleValue] = arr.splice(middleIndex, 1);
    // 第二步：准备左右两个数组，循环数组中剩余的项，比中间项小的放到左数组中，反之放到右数组中
    const leftArr = [];
    const rightArr = [];
    for (let i = 0; i < arr.length; i++) {
        const item = arr[i];
        item < middleValue ? leftArr.push(item) : rightArr.push(item);
    }
    // 第三步：采用递归让左右两边的数组继续这样处理，直到左右两边都排好序
    return quick(leftArr).concat(middleValue, quick(rightArr));
}

console.log(quick(arr));

const arr = [12, 6, 23, 4, 36, 18, 16];

function quick(arr) {
    // 第四步：结束递归(当arr中小于等于一项，则不用继续递归处理)
    if (arr.length <= 1) {
        return arr;
    }
    // 第一步：直接将数组第一项作为中间项
    // 第二步：准备左右两个数组，循环数组中剩余的项，比中间项小的放到左数组中，反之放到右数组中
    const leftArr = [];
    const rightArr = [];
    const firstValue = arr[0];
    // 从第二项开始循环处理。
    for (let i = 1; i < arr.length; i++) {
        const item = arr[i];
        item < firstValue ? leftArr.push(item) : rightArr.push(item);
    }
    // 第三步：采用递归让左右两边的数组继续这样处理，直到左右两边都排好序
    return quick(leftArr).concat(firstValue, quick(rightArr));
}

console.log(quick(arr));

/*
 寻找第i小的数的位置，放到i位置上
 */
const arr = [12, 6, 23, 4, 36, 18];

function selectSort(arr) {
    const len = arr.length;
    for (let i = 0; i < len; i++) {
        let minIndex = i;
        for (let j = i + 1; j < len; j++) {
            minIndex = arr[j] <= arr[minIndex] ? j : minIndex;
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}

console.log(selectSort(arr));

function MergeSort (arr, low, high) {
    const length = arr.length
    if (low === high) {
        return arr[low]
    }
    const mid = Math.floor((low + high)/2)
    MergeSort(arr, low, mid)
    MergeSort(arr, mid + 1, high)
    merge(arr, low, high)
    return arr

}

function merge (arr, low, high) {
    const mid = Math.floor((low + high)/2)
    let left = low
    let right = mid + 1
    const result = []
    while (left <= mid && right <= high) {
        if (arr[left] <= arr[right]) {
            result.push(arr[left++])
        } else {
            result.push(arr[right++])
        }
    }
    while (left <= mid) {
        result.push(arr[left++])
    }
    while (right <= high) {
        result.push(arr[right++])
    }

    arr.splice(low, high-low+1, ...result)
}

const test = [2, 34, 452,3,5, 785, 32, 345, 567, 322,5]

console.log(MergeSort(test, 0, test.length - 1))

function ShellSort (arr) {
    const length = arr.length
    let gap = Math.floor(length)
    while (gap) {
        for (let i = gap; i < length; i++) {
            const temp = arr[i]
            let j
            for (j = i - gap; j >= 0 && temp < arr[j]; j = j - gap) {
                arr[j + gap] = arr[j]
            }
            arr[j + gap] = temp
        }
        gap = Math.floor(gap / 2)
    }
    return arr
}

function HeapSort (arr) {
    const length = arr.length

    // 调整初始堆，调整完其实也确定了最大值
    // 但此时最大值是在 arr[0] 中
    for (let i = Math.floor(length/2) - 1; i >= 0; i--) {
        adjustHeap(arr, i, length)
    }

    // 把 arr[0](最大值)换到后面
    for (let i = length - 1; i >=0; i--) {
        const temp = arr[0]
        arr[0] = arr[i]
        arr[i] = temp
        adjustHeap(arr, 0, i)
    }

    return arr
}

// size 是还需要调整的堆的大小
// 随着一个个最大值的确定，size 会越来越小
function adjustHeap (arr, position, size) {
    const left = position * 2 + 1
    const right = left + 1
    let maxIndex = position
    if (left < size && arr[left] > arr[maxIndex]) {
        maxIndex = left
    }
    if (right < size && arr[right] > arr[maxIndex]) {
        maxIndex = right
    }
    if (maxIndex !== position) {
        const temp = arr[position]
        arr[position] = arr[maxIndex]
        arr[maxIndex] = temp
        adjustHeap(arr, maxIndex, size)
    }
    return arr
}

const arr = [1, 3, 5, 7, 9, 10];
const target = 7;

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        const midIndex = Math.floor((left + right) / 2);
        if (arr[midIndex] > target) {
            right = midIndex - 1;
        } else if (arr[midIndex] < target) {
            left = midIndex + 1;
        } else {
            return midIndex;
        }
    }
    return -1;
}

const index = binarySearch(arr, target);
console.log(index); // 3